hackMD原稿

今天要來實作一個很有趣的題目，就是圍棋的征子，這邊會用上很多前幾天所分享到的演算法，剛好當作複習。
這邊一樣不浪費篇幅寫規則，這邊附上維基百科的傳送門：圍棋基礎規則。
這邊還有圍棋進階規則，說真的很多進階規則我自己也搞不太懂，像是假生，我也是在當圍棋替代役的時候聽棋協的秦秘書長說的。

想學圍棋的話可以報名黑嘉嘉圍棋教室基礎課，裡面很多AI功能都是我與正在UCLA讀博士的Steven大大做的，所以自行業配一波XDD。

征子

征子是圍棋的一種吃子技巧，如下圖此時黑棋只要下在A位，無論白棋如何掙扎都是無法逃脫的。

征子會讓對方棋子始終保持在1~2氣的狀態，從1氣被叫吃，跑一手後仍只有2氣，只要進攻方注意到緊氣的位置，就能以這種方式把對方給吃掉。

征子對下圍棋的人來說是個非常基礎的吃子技巧，但將征子給實作出來就沒那麼容易了，有很多小細節藏在裡面。
大家可以先停在這裡思考一下，回想一下前幾天所分享到的各種演算法，試著動手寫寫看再回來繼續往下看。

實作

資料結構

最簡單的就是使用二維陣列來表示盤面狀態，這邊以9路棋盤為例：黑棋為X、白棋為O、空為.
例：

board = [
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "X", ".", "."],
    [".", ".", ".", ".", ".", "X", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."]
]

開始實作征子前要先根據圍棋的規則完成一些小功能。

判斷同塊棋與氣

首先要先判斷哪些棋子是連接在一起的，只要是相連的棋就視為同一塊，還要紀錄氣的位置，簡單說就是同一塊棋旁邊的空位就是這塊棋的氣。
想法上就是用遞迴去解，從目標棋子開始，往上下左右四個方向找，如果也是自己的棋，就把這顆子加入棋塊，然後再對這顆子的上下左右去找，為了避免回頭重複找，所以要記錄找過的地方。

# 定義棋盤大小
BOARD_SIZE = 9

# 定義方向 (上下左右)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_in_bounds(x, y):  # 檢查座標是否在棋盤內
    return 0 <= x < BOARD_SIZE and 0 <= y < BOARD_SIZE

board 表示棋盤的二維陣列。
visited 用來存已經訪問過的點。
stones 儲存棋串。
liberties 氣的英文好像都是翻成liberty，我也不知道為什麼，這邊用set來存是因為有可能同一個氣被重複計算到，直接用set比較方便。

例如下圖，A點會被上跟左兩顆黑棋重複計算到。

def get_stones_and_liberties(board, x, y):
    if board[x][y] == '.':
        return [], []

    visited = set()  # 已訪問過的點
    stones = []  # 儲存棋串中所有的棋子位置
    liberties = set()  # 記錄該棋串的氣
    color = board[x][y]  # 棋子的顏色

    # 深度優先搜尋 (DFS)
    def dfs(x, y):
        # 避免重複訪問
        if (x, y) in visited:
            return

        visited.add((x, y))   # 標記已訪問過
        stones.append((x, y))  # 將該點加入棋串

        # 檢查四個方向
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy
            # 檢查是否在邊界內
            if is_in_bounds(nx, ny):
                if board[nx][ny] == '.':
                    # 如果是空點，記錄為氣
                    liberties.add((nx, ny))
                elif board[nx][ny] == color:
                    # 如果是同顏色的棋子，繼續搜尋
                    dfs(nx, ny)

    # 從輸入的位置開始搜尋
    dfs(x, y)

    return stones, liberties

這邊應該還蠻簡單的，很像修資料結構演算法時，老師會出的小作業。

判斷征子

接下來要進入到征子最重要的部分了，我們要判斷黑棋能不能吃掉白棋，如果我們單純的使用Minimax + Alpha-Beta Pruning的話，應該是非常難在有限的時間內跑出解來，畢竟光是9x9的棋盤也已經過於複雜。
但是這邊因為是要判斷征子，我們就要利用征子的特性，讓對方的棋子始終保持在1~2氣之間的狀態，所以我們就可以通過類似Threat Space Search的概念，將搜索範圍限縮在「緊氣」的點上，而白棋被「叫吃」就只能逃跑，會大幅減少搜索難度。

進攻方嘗試緊氣去吃掉對方，防守方要逃跑增加氣，所以要先標註出氣的位置，這就會利用到前面寫的get_stones_and_liberties了，進攻方把所有能緊氣的地方都試下看看，由於征子的特性，進攻方在進攻時讓目標棋子的氣大於2氣則為失敗，目標棋子只剩1氣時，因為輪到進攻方下，此時就可以直接將對方吃掉，就是征子成功，目標棋子為0氣那就更不用說了當然就是已經吃掉了。

target 為目標棋子，如果是一塊棋那給其中一顆棋子的座標即可。
color 為先手方顏色，O或X
target_color 為目標棋子顏色
opponent_color 對方棋子顏色

如果先手方顏色與目標顏色不同，那先手方則為進攻方，顏色相同就當然是防守方了~

def is_ladder(board, target, color):
    if (board[target[0]][target[1]] == '.'):
        return 0

    target_color = board[target[0]][target[1]]  # 目標棋子顏色
    opponent_color = 'X' if color == 'O' else 'O'  # 對方顏色
    stones, liberties = find_stones_and_liberties(board, target[0], target[1])

    # 進攻方 (max層)
    if color != target_color:
        if len(liberties) > 2:
            return 0  # 目標大於2氣 失敗
        if len(liberties) <= 1:
            return 1  # 目標氣少於等於1 成功
        score = -10
        for x, y in liberties:
            board[x][y] = color
            score = max(is_ladder(board, target, opponent_color), score)
            board[x][y] = '.'
            if score == 1:
                break

    # 防守方 (min層)
    if color == target_color:
        if len(liberties) >= 2:
            return 0  # 防守方有2個或以上的氣，逃脫成功
        score = 10
        for x, y in liberties:
            board[x][y] = color
            score = min(is_ladder(board, target, opponent_color), score)
            board[x][y] = '.'
            if score == 0:
                break
    
    return score

如果能吃掉會回傳1，吃不掉會回傳0，最後附上一個印出棋盤的功能方便大家印出棋盤測試。

def print_board(board):
    index_A = 'abcdefghijklmnopqrs'
    size = len(board)
    index_A = index_A[0:size]
    for c in ' '+index_A:
        print(c, end=' ')
    print()
    for i, line in enumerate(board):
        print(index_A[i], end=' ')
        for value in line:
            print(value, end=' ')
        print()
    print()

以下是測試範例，board1應該要回傳1，board2應該要回傳0。

board1 = [
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "X", ".", "."],
    [".", ".", ".", ".", ".", "X", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."]
]

board2 = [
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "X", ".", "."],
    [".", ".", ".", ".", ".", "X", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", "O", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."]
]

總結

在實作圍棋征子邏輯的過程，我們用到了Minimax Algorithm、Alpha-Beta Pruning，利用氣來縮小搜索空間，類似於Threat Space Search的概念，希望大家在複習前面所學時，也能同時感受到圍棋的趣味。

特殊情況思考

這個範例其實是征子失敗的，但如果是按照上面的程式會回傳1。
這邊就留給大家思考是為什麼了，這幾天太肝了，只好拆成兩篇，明天再來解答。

board = [
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "X", ".", "."],
    [".", ".", ".", ".", ".", "X", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "O", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."]
]